• A graph G consists of a set of vertices V(G) = {v₁, v₂, …, v_n} and a set of

edges E(G) = {e₁, e₂, …, e_m}. The edges of G join any pair of vertices of G.

• We write e = {v_i, v_j} = v_iv_j. If v_iv_{j Î} E(G), then v_i and v_j are adjacent (i.e. there is an edge connecting v_i and v_j).
• If e = v_i v_i, we call e a loop.

• A subgraph H of G is a graph where V(H) Í V(G) and E(H) Í E(G).
• An induced subgraph is a subgraph H of G whose edges are all edges in G whose verticies are in V(H).

• A simple graph G has no loops, and no two edges in G connect the same pair of vertices.
• A complete graph is a simple graph containing an edge between every pair of (distinct) verticies.

Note: K_n denotes the complete graph with n verticies.

Claim: A complete graph G with n verticies has n(n-1)/2 edges.

Proof: (by induction)

If n=1, then G has no edges. So 1(1-1)/2 = 0.

Now, suppose our claim holds for a particular number of verticies, say k. So if G has k verticies, then the number of edges in G is k(k-1)/2.

Now let’s look at G when we add one more vertex. In order to make it a complete graph we will have to add k edges to G. So now the number of edges in G will be:

k(k-1)/2 + k = [k(k-1) +2k]/2 = k(k+1)/2 = (k+1)(k+1-1)/2.

• The degree of a vertex v Î V(G) is the number of edges of which v is an end.
• A graph is regular of degree k (or k-regular) if every v Î V(G) has degree k.

First Theorem of Graph Theory: The sum of the degrees of each vertex in a graph G is equal to twice the number of edges of G.

• A walk of length L from v_i to v_j in a graph G is a finite sequence of verticies of G, u₀ u₁ … u_L , where u₀ = v_i and u_L= v_j , and u_t-1 u_{t Î} E(G) for 1 £ t £ L.
• A graph is connected if each pair of vertices is joined by a walk.
• A cycle is a walk with no repeated edge where "last vertex = first vertex" is the only vertex repetition (the endpoints are equal).

• A path is a walk with no repeated vertex.

Claim: If u and v are distinct verticies in G, then every walk from u to v contains a path from u to v.

Proof: (using stong induction). We want to prove that every walk W of length L from u to v contains a path from u to v.

If L = 1, the only edge of W is uv, so W is itself a path from u to v.

Now, suppose that L > 1 and our claim holds for all walks shorter than W. If W has no repeated vertex then it is already a path from u to v. If W does have a repeated vertex, then we can remove the edges and vertices of W that are between the appearances of the repeated vertex to obtain a shorter walk W’ from u to v contained in W. And by our induction hypothesis, W’ contains a path from u to v and we built it so it is contained in W.

• We can efficiently describe a graph by specifying its adjacency matrix. We define the adjacency matrix of a graph G with n verticies as the n x n matrix A(G) where

a_ij = number of edges between v_i and v_j

a_ij = 0, if v_i and v_j are not adjacent

Note: A is a real symmetric matrix.

Note: For a simple graph,

1. the diagonal entries of A are 0
2. trace (A) = 0
3. all entries off the diagonal are either 0 or 1.

Theorem: If A is the adjacency matrix of a simple graph G, then the ij-th entry a_ij^(k) of the matrix A^k is equal to the number of walks of length k from vertex v_i to v_j.

Claim: If G is a k-regular graph, then k is an eigenvalue of A(G).

Proof: Since every vertex of G has an edge to k other verticies, the sum of each row of A(G) is equal to k. If we let u = [1 1 1 … 1]^T, then Au = [k k k … k]^T = ku, so k is an eigenvalue of A(G).

• We can talk about isomorphisms of graphs. An isomorphism from a graph G to a graph H is a one-to-one and onto function f : V(G) à V(H) such that v_iv_{j Î} E(G) if and only if f (v_i)f (v_j) Î E(H). We can think of a graph isomorphism as preserving the adjacency relation by permuting the rows and columns of A(G) to obtain A(H). In other words, if two verticies are adjacent in G, then their images in H are adjacent as well. If there exists an isomorphism from G to H, then G » H.

Claim: Graph isomorphism is an equivalence relation.

Proof: Reflexive: the identity map on V(G) is an isomorphism from G to G.

So G » G.

Symmetric: if f is an isomorphism from G to H, then f ^-1 is an isomorphism from H to G, so G » H Þ H » G.

Transitive: if f is an isomorphism from G to H and y is an isomorphism from H to J, then the composition mapping f o y is a one-to-one and onto function from V(G) to V(J) that preserves the adjacency relation, therefore there exists an isomorphism from G to J. So G » H and H » J Þ G » J.

• The complement G’ of a simple graph G is the simple graph with V(G’) = V(G) and uv Î E(G’) if and only if uv Ï E(G).

Claim: G » H if and only if G’ » H’.

Proof: (Þ )

G » H Þ there exists an isomorphism f : V(G) à V(H) such that v_iv_{j Î} E(G) Þ f (v_i)f (v_j) Î E(H) [Eq. 1].

Note: V(G) = V(G’) and V(H) = V(H’), and

v_iv_j Ï E(G) Þ f (v_i)f (v_j) Ï E(H) [Eq. 2].

We know v_iv_j Ï E(G) Þ v_iv_j Î E(G’) and f (v_i)f (v_j) Ï E(H) Þ f (v_i)f (v_j) Î E(H’).

Now we substitute equivalent statements into [Eq. 2] to get: v_iv_{j Î} E(G’) Þ f (v_i)f (v_j) Î E(H’), so G’ » H’.

(Note: The proof of (Ü ) is very similar.)

• How can we minimize the cost of laying cable where every telephone is connected to every other?

• Depth-First Search: a method of traversing through a graph G and "visiting" each vertex of G. We start at a particular vertex v Î V(G) and recursively visit each vertex adjacent to v.

• A Hamiltonian tour is a path or cycle that visits each v Î V(G) exactly once.

• A weighted graph is a graph with numerical values assigned to each edge. A good example is a map of airline flights and the distance for each flight.

• Dijkstra’s Algorithm: (a.k.a. Single-Source Shortest Paths)

• How can we schedule final exam sessions so that no student has two final exams scheduled at the same time?

• A k-coloring of a graph G is a labeling f: V(G) à {1, 2, …, k}. We call the labels colors. A graph G is k- colorable if v_iv_{j Î} E(G) Þ f(v_i) ¹ f(v_j). The chromatic number c (G) is the minimum value of k such that G is k-colorable.

Claim: c (K_n ;k) = k(k-1)…(k-n+1).

• The chromatic polynomial of G is the function c (G;k) which counts the number of mappings f: V(G) à {1, 2, …, k} which make G k-colorable.

Biggs, Norman. Algebraic Graph Theory, Second Edition. Cambridge University Press, 1993.

Gibbons, Alan. Algorithmic Graph Theory. Cambridge University Press, 1985.

West, Douglas B. Introduction to Graph Theory. Prentice Hall, 1996.